/*
动态规划，最重要的是理解思想
https://blog.csdn.net/mu399/article/details/7722810
https://www.jianshu.com/p/a66d5ce49df5
黄色格子和绿色格子代表每个物品的重量和价值，浅蓝色格子代表背包剩余的空间。
如第一个浅蓝色格子1，表示背包剩余1个空间，那对于5个物品，都不能放入，都是0的可能性；背包空间剩2的情况下，可能放第一个物品或第二个物品，价值最大的就是第一个物品，是6。
浅蓝色格子下面每一行，代表的是遇到这个物品，所能做出的选择得到的最大值。
首先要明确，这张表是至底向上，从左到右生成的。
从最后一行看，当背包空间剩余1,2,3时，无法放入重量为4的物品，但从4开始，就可以放入这个重量为4的物品，到后面空间为10，也只能放入一个重量为4的物品（因为同样的物品只有一个），以这个物品做出的所有选择就枚举完成了。
再看倒数第二行，此时考虑的就是d和e这两件物品了，对于d，有可选和不选两种情况。不选的情况下，只有1件e能选，即回到第一种情况，选择d的情况下，在背包剩余9之前，都是放e的价值最大，到9的时候，选择先放d，减5个空间，余4个空间,4空间的时候最大价值是e的6，可以同时放d和e了。
此时比较的就是第一次的最大情况6和第二次的6+4进行比较，得出10更大的组合情况
依次类推，倒数第3行，此时有c、d、e三个物品可以选择。对于c有选择和不选两种情况。
不选c的情况下，最大值还是上次的最大值10；选择c时，占用6个空间，价值是5，还剩4个空间，4个空间的可选最大值是6，5+6=11>上次的最大值10，所以选择c是价值最大的组合。
这样理解01背包的动态规划算法，本质上就是填表
 */
package com.test.zero1package;

public class DynamicProgramming {

    static int[] w = {2,3,4,5};
    static int[] v = {3,4,5,6};
    static int capacity=9;

    public static void main(String[] args) {
        value();
    }

    static void value() {
        int[][] arr = new int[5][capacity + 1]; //表格的行首和列头都加一个0的列
        for (int i = 1; i <= 4 ; i++) {  //第一个循环代表物品的循环，1个物品1个物品的循环，相当于表格的行
            for (int j = 1; j <= capacity; j++) {  //填表，容量的循环，容量从0开始到最大，填充的是当前行的每列
                //加一个判断条件，如果当前容量小于选择的当前物品容量，肯定放不进去，直接跳过
                if(w[i-1] <= j) {
                    //以倒数第二排的最大容量来说，比较的就是放倒数第二个物品d后的价值+剩余容量可以放的最大值，与不放倒数第二个物品的最大值情况进行比较，谁更大就选谁
                    arr[i][j] = Math.max(arr[i-1][j], arr[i-1][j-w[i-1]] + v[i-1]); //动态规划状态转移方程，对比青蛙跳台阶理解
                    //arr[i][j]表示从当前单元格，arr[i-1][j]表示倒数前一行对应的这一列，arr[i-1][j-w[i-1]]表示选择当前物品后的价值+剩余空间能选择的最大价值（即倒数上一行的当前空间最大值）
                }else{
                    arr[i][j] =arr[i-1][j]; //否则直接等于上一次最大的情况
                }

            }

        }
        //使用增强for循环打印
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
    }
}
